package org.example.myleet.p733;

public class Solution {

    private static final int[][] DIRECTIONS = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int nr = image.length, nc = image[0].length;
        boolean[][] visited = new boolean[nr][nc];
        int sColor = image[sr][sc];
        int size = 0;
        int[][] stack = new int[nr * nc][2];
        //push
        stack[size++] = new int[]{sr, sc};
        while (size > 0) {
            int len = size;
            for (int i = 0; i < len; ++i) {
                //pop
                int[] p = stack[--size];
                visited[p[0]][p[1]] = true;
                image[p[0]][p[1]] = newColor;
                for (int[] DIRECTION : DIRECTIONS) {
                    int[] np = new int[]{p[0] + DIRECTION[0], p[1] + DIRECTION[1]};
                    if (0 <= np[0] && np[0] < nr && 0 <= np[1] && np[1] < nc) {
                        if ((!visited[np[0]][np[1]]) && image[np[0]][np[1]] == sColor) {
                            stack[size++] = np;
                        }
                    }
                }
            }
        }
        return image;
    }
}
